For every node in a network to be able to exchange traffic with every other node, the intermediate nodes between every possible combination of endpoints (i.e., source and destination) must know the direction in which to send traffic so that the traffic can be advanced closer to its destination. In the following, intermediate nodes adapted to decide which path to use for forwarding traffic in this manner are referred to as routers.
It is possible for a router to know of more than one path for reaching a particular destination. For reasons such as choosing the optimal path and choosing a path consistent with administrative or technical policy, it is necessary for a router to analyze the information it receives from various sources and select the path it wishes to use for the particular destination. This decision process is referred to as “routing”.
A “routing table” is used by a router to help it make its routing decisions. A routing table inside a router typically includes all the information that the router knows about the topology of the network in terms of links and locations of destinations. A given router's understanding of the topology of the network can come from sources such as static configuration and dynamic routing protocols. Examples of commonly used dynamic routing protocols include both exterior gateway protocols and interior gateway protocols such as border gateway protocol (BGP), open shortest path first (OSPF) and intermediate system to intermediate system (IS-IS), among others.
Based upon the information in the routing table, the router makes decisions about which path to use for each particular destination, thereby resulting in the creation of a forwarding table. When a router subsequently receives a packet on an interface, it looks up the destination address of the packet in the forwarding table and performs a switching operation, causing the packet to emerge at the particular interface specified in the forwarding table. In this way, the router gets the packet closer to its destination. The acts of receiving a packet, performing a lookup in the forwarding table and sending the packet via the appropriate interface are collectively referred to as “forwarding”.
It is known that the amount of routing information and the size of a router's routing and forwarding tables increases with the number of interfaces and with the number of possible destination nodes. Given the existing state of memory density and processing speed in the industry, this places a boundary on the number of interfaces that can be supported by the router, depending on the bandwidth of each interface. For instance, the number of high-speed interfaces that can be supported by some of the most advanced routers given the current configuration of the Internet is limited to about 8-16. At a rate of 10 Gbps per interface, this provides an aggregate routing capacity on the order of 160 Gbps.
An aggregate routing capacity of this magnitude may conceivably be sufficient to support a relatively slow expansion of the Internet, as was the case when connectivity was limited to a single backbone (known as NSFNET) and restricted to government, educational and military institutions as well as a handful of Internet service providers (ISPs). In late 1994 and early 1995, the NSFNET backbone was decommissioned and since then, the addition of commercial and private interests to the Internet community has caused the number of reachable computers on the Internet to skyrocket. This, coupled with a steady rise in the average bandwidth of individual connections as end users begin to make more use of graphics-intensive services, has resulted in a dramatic increase in the amount of traffic circulating on the Internet, leading, in turn, to a heightened demand on routers to handle greater aggregate capacities. If the existing trend continues, aggregate capacities far exceeding 160 Gbps and interfaces numbering far more than 16 will be required of the next generation of routers.
Unfortunately, conventional approaches to increasing router capacity and interface density offer merely incremental improvements and do not scale easily when the aggregate routing capacity and number of interfaces needs to be increased by several orders of magnitude. An important factor contributing to this difficulty is the huge amount of routing information received from each of a large number of interfaces. Firstly, the sheer volume of the received routing information and of the associated forwarding tables becomes prohibitively large and thus virtually impossible to store in the memory of a single controller card. Secondly, the time to access and process the received routing information increases to a point beyond which the delay in responsiveness to a topological change in the network becomes unacceptable.
An additional factor contributing to the difficulty of scaling a traditional router is the fact that as the Internet evolves from a best-effort network to one with different classes of service and penalty-based service level agreements (SLAs), each link has increasingly complex cost attributes and the optimal path between destinations may be different for different classes of service. The increasing complexity of the calculations on a per-link basis further compounds the complexity of managing and increasing the number of line cards and interfaces.
Thus, there continues to be a requirement in the industry to provide a router that is scalable to high aggregate capacities and to a large number of interfaces, with the aim of satisfying anticipated increases in the bandwidth demand of the global Internet user community.